package oj;

public class Num0204 {
    public ListNode partition(ListNode head, int x) {
        if(head == null){
            return null;
        }
        ListNode pGreatHead = new ListNode();
        ListNode pGreatTail = pGreatHead;
        ListNode pLessHead = new ListNode();
        ListNode pLessTail = pLessHead;

        while(head != null){
            if(head.val < x){
                pLessTail.next = head;
                pLessTail = head;
            }else{
                pGreatTail.next = head;
                pGreatTail = head;
            }
            head = head.next;
        }
        pLessTail.next = pGreatHead.next;
        pGreatTail.next = null;
        head = pLessHead.next;
        return head;
    }
}
